package leetcode_zh

/**
 * @Description: 4. 寻找两个正序数组的中位数 困难
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/2 8:28
 **/
func findMedianSortedArrays04(nums1 []int, nums2 []int) float64 {
	var n = len(nums1) + len(nums2)
	// 偶数长度
	if n&1 == 0 {
		var left = findKthNum(nums1, nums2, n/2)
		var right = findKthNum(nums1, nums2, n/2+1)
		return (left + right) / 2
	}
	// 奇数
	return findKthNum(nums1, nums2, n/2+1)
}

func findKthNum(nums1, nums2 []int, k int) float64 {
	if len(nums1) > len(nums2) {
		return findKthNum(nums2, nums1, k)
	}
	if len(nums1) == 0 {
		return float64(nums2[k-1])
	}
	if k == 1 {
		return float64(getMin(nums1[0], nums2[0]))
	}
	var idx1 = getMin(len(nums1), k/2)
	var idx2 = k - k/2
	if nums1[idx1-1] < nums2[idx2-1] {
		return findKthNum(nums1[idx1:], nums2, k-idx1)
	}
	return findKthNum(nums1, nums2[idx2:], k-idx2)
}
